// Contestants do not need to worry about anything in this file. This is just
// helper code that does the boring stuff for you, so you can focus on the
// interesting stuff. That being said, you're welcome to change anything in
// this file if you know what you're doing.

import java.util.*;
import java.io.*;

public class PlanetWars {
    // Store all the planets and fleets. OMG we wouldn't wanna lose all the
    // planets and fleets, would we!?

    private ArrayList<Planet> planets;
    private ArrayList<Fleet> fleets;
    private ArrayList<StringBuilder> orders;
    // Store the fleets and planets (by player) to avoid iterating each time
    // you need them
    private ArrayList<Planet> myPlanets;
    private ArrayList<Planet> enemyPlanets;
    private ArrayList<Planet> neutralPlanets;
    private ArrayList<Planet> notMyPlanets;
    private ArrayList<Fleet> myFleets;
    private ArrayList<Fleet> enemyFleets;
    private int turn = 0;
    private int myProduction;
    private int enemyProduction;

    private class Order {

        private int source;
        private int destination;
        private int ships;

        public Order(int sourcePlanet, int destinationPlanet, int numShips) {
            source = sourcePlanet;
            destination = destinationPlanet;
            ships = numShips;
        }

        public StringBuilder getStringBuilder() {
            StringBuilder sb = new StringBuilder();
            sb.append(source);
            sb.append(" ");
            sb.append(destination);
            sb.append(" ");
            sb.append(ships);
            sb.append("\n");
            return sb;
        }
    }

    // Constructs a PlanetWars object instance, given a string containing a
    // description of a game state.
    public PlanetWars(String gameStateString) {
        planets = new ArrayList<Planet>();
        fleets = new ArrayList<Fleet>();
        orders = new ArrayList<StringBuilder>();
        myPlanets = new ArrayList<Planet>();
        enemyPlanets = new ArrayList<Planet>();
        neutralPlanets = new ArrayList<Planet>();
        notMyPlanets = new ArrayList<Planet>();
        myFleets = new ArrayList<Fleet>();
        enemyFleets = new ArrayList<Fleet>();
        myProduction = 0;
        enemyProduction = 0;
        ParseGameState(gameStateString);
    }

    public PlanetWars() {
        planets = new ArrayList<Planet>();
        fleets = new ArrayList<Fleet>();
        orders = new ArrayList<StringBuilder>();
        myPlanets = new ArrayList<Planet>();
        enemyPlanets = new ArrayList<Planet>();
        neutralPlanets = new ArrayList<Planet>();
        notMyPlanets = new ArrayList<Planet>();
        myFleets = new ArrayList<Fleet>();
        enemyFleets = new ArrayList<Fleet>();
        myProduction = 0;
        enemyProduction = 0;
    }

    public int Turn() {
        return turn;
    }

    // Returns the number of planets. Planets are numbered starting with 0.
    public int NumPlanets() {
        return planets.size();
    }

    // Returns the planet with the given planet_id. There are NumPlanets()
    // planets. They are numbered starting at 0.
    public Planet GetPlanet(int planetID) {
        return planets.get(planetID);
    }

    // Returns the number of fleets.
    public int NumFleets() {
        return fleets.size();
    }

    // Returns the fleet with the given fleet_id. Fleets are numbered starting
    // with 0. There are NumFleets() fleets. fleet_id's are not consistent from
    // one turn to the next.
    public Fleet GetFleet(int fleetID) {
        return fleets.get(fleetID);
    }

    //Removes the specified fleet from the list
    public void RemoveFleet(Fleet f) {
        fleets.remove(fleets.indexOf(f));
    }

    // Returns a list of all the planets.
    public List<Planet> Planets() {
        return planets;
    }

    // Return a list of all the planets owned by the current player. By
    // convention, the current player is always player number 1.
    public List<Planet> MyPlanets() {
        return myPlanets;
    }

    // Return a list of all neutral planets.
    public List<Planet> NeutralPlanets() {
        return neutralPlanets;
    }

    // Return a list of all the planets owned by rival players. This excludes
    // planets owned by the current player, as well as neutral planets.
    public List<Planet> EnemyPlanets() {
        return enemyPlanets;
    }

    // Return a list of all the planets that are not owned by the current
    // player. This includes all enemy planets and neutral planets.
    public List<Planet> NotMyPlanets() {
        return notMyPlanets;
    }

    // Return a list of all the fleets.
    public List<Fleet> Fleets() {
        return fleets;
    }

    // Return a list of all the fleets owned by the current player.
    public List<Fleet> MyFleets() {
        return myFleets;
    }

    // Return a list of all the fleets owned by enemy players.
    public List<Fleet> EnemyFleets() {
        return enemyFleets;
    }

    public List<Planet> PlanetsSortedByDistance(int sourcePlanet, List<Planet> planets) {
        DistanceComparator dc = new DistanceComparator(sourcePlanet);
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    public List<Planet> PlanetsSortedByDistance(Planet source, List<Planet> planets) {
        DistanceComparator dc = new DistanceComparator(source.PlanetID());
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    private class DistanceComparator implements Comparator<Planet> {

        private int planetID;

        public DistanceComparator(Planet source) {
            planetID = source.PlanetID();
        }

        public DistanceComparator(int ID) {
            planetID = ID;
        }

        public int compare(Planet p1, Planet p2) {
            int d1 = Distance(planetID, p1.PlanetID());
            int d2 = Distance(planetID, p2.PlanetID());
            if (d1 > d2) {
                return 1;
            } else if (d2 > d1) {
                return -1;
            }
            return 0;
        }
    }

    public List<Planet> PlanetsSortedByStrength(List<Planet> planets) {
        StrengthComparator dc = new StrengthComparator();
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    private class StrengthComparator implements Comparator<Planet> {

        public int compare(Planet p1, Planet p2) {
            int d1 = p1.NumShips();
            int d2 = p2.NumShips();
            if (d1 > d2) {
                return 1;
            } else if (d2 > d1) {
                return -1;
            }
            return 0;
        }
    }

    public List<Planet> PlanetsSortedByNetStrength(List<Planet> planets) {
        NetStrengthComparator dc = new NetStrengthComparator();
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    private class NetStrengthComparator implements Comparator<Planet> {

        public int compare(Planet p1, Planet p2) {
            int d1 = PlanetNetStrength(p1.PlanetID());
            int d2 = PlanetNetStrength(p2.PlanetID());
            if (d1 > d2) {
                return 1;
            } else if (d2 > d1) {
                return -1;
            }
            return 0;
        }
    }

    public List<Planet> FirstNPlanets(List<Planet> planets, int n) {
        if (n > planets.size()) {
            return planets;
        }
        return planets.subList(0, n);
    }

    public Coord CenterOfPoints(List<Coord> points) {
        double x = 0;
        double y = 0;
        for (Coord c : points) {
            x += c.X();
            y += c.Y();
        }
        x = x / points.size();
        y = y / points.size();
        return new Coord(x, y);
    }

    public Coord CenterOfPlanets(List<Planet> planets) {
        double x = 0;
        double y = 0;
        for (Planet c : planets) {
            for (int i = 0; i < c.GrowthRate(); i++) {
                x += c.X();
                y += c.Y();
            }
        }
        x = x / planets.size();
        y = y / planets.size();
        return new Coord(x, y);
    }

    public Coord CenterOfPointsAndPlanets(List<Coord> points, List<Planet> planets) {
        double x = 0;
        double y = 0;
        for (Coord c : points) {
            x += c.X();
            y += c.Y();
        }
        for (Planet c : planets) {
            x += c.X();
            y += c.Y();
        }
        x = x / (points.size() + planets.size());
        y = y / (points.size() + planets.size());
        return new Coord(x, y);
    }

    public List<Planet> PlanetsSortedByValue(int sourcePlanet, List<Planet> planets, double distanceWeight, double growthWeight, double strengthWeight) {
        ValueComparator dc = new ValueComparator(sourcePlanet, distanceWeight, growthWeight, strengthWeight);
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    public List<Planet> PlanetsSortedByValue(Planet source, List<Planet> planets, double distanceWeight, double growthWeight, double strengthWeight) {
        ValueComparator dc = new ValueComparator(source.PlanetID(), distanceWeight, growthWeight, strengthWeight);
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    public List<Planet> PlanetsSortedByValue(Coord source, List<Planet> planets, double distanceWeight, double growthWeight, double strengthWeight) {
        ValueComparator dc = new ValueComparator(source, distanceWeight, growthWeight, strengthWeight);
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    private class ValueComparator implements Comparator<Planet> {

        private int planetID = -1;
        private double distW;
        private double growthW;
        private double strengthW;
        private Coord c;

        public ValueComparator(Planet source, double distanceWeight, double growthWeight, double strengthWeight) {
            planetID = source.PlanetID();
            distW = distanceWeight;
            growthW = growthWeight;
            strengthW = strengthWeight;
        }

        public ValueComparator(int ID, double distanceWeight, double growthWeight, double strengthWeight) {
            planetID = ID;
            distW = distanceWeight;
            growthW = growthWeight;
            strengthW = strengthWeight;
        }

        public ValueComparator(Coord coord, double distanceWeight, double growthWeight, double strengthWeight) {
            c = coord;
            distW = distanceWeight;
            growthW = growthWeight;
            strengthW = strengthWeight;
        }

        public int compare(Planet p1, Planet p2) {
            double d1;
            double d2;
            if (planetID >= 0) {
                d1 = PlanetValue(planetID, p1.PlanetID(), distW, growthW, strengthW);
                d2 = PlanetValue(planetID, p2.PlanetID(), distW, growthW, strengthW);
            } else {
                d1 = PlanetValue(c, p1, distW, growthW, strengthW);
                d2 = PlanetValue(c, p2, distW, growthW, strengthW);
            }
            if (p1.GrowthRate() == 0) {
                return 1;
            }
            if (d1 > d2) {
                return 1;
            } else if (d2 > d1) {
                return -1;
            }
            return 0;
        }
    }

    public List<Planet> PlanetsSortedByGrowth(List<Planet> planets) {
        GrowthComparator dc = new GrowthComparator();
        List<Planet> sortedPlanets = new ArrayList<Planet>(planets);
        Collections.sort(sortedPlanets, dc);
        return sortedPlanets;
    }

    private class GrowthComparator implements Comparator<Planet> {

        public int compare(Planet p1, Planet p2) {
            int d1 = p1.GrowthRate();
            int d2 = p2.GrowthRate();
            if (d1 > d2) {
                return -1;
            } else if (d2 > d1) {
                return 1;
            }
            return 0;
        }
    }

    public Planet ClosestTo(int sourcePlanet, List<Planet> planets) {
        int min_distance = Integer.MAX_VALUE;
        Planet closest = null;
        for (Planet p : planets) {
            if (p.PlanetID() != sourcePlanet) {
                int distance = Distance(sourcePlanet, p.PlanetID());
                if (distance < min_distance) {
                    min_distance = distance;
                    closest = p;
                }
            }
        }
        return closest;
    }

    public Planet ClosestTo(Planet source, List<Planet> planets) {
        int min_distance = Integer.MAX_VALUE;
        Planet closest = null;
        for (Planet p : planets) {
            if (p.PlanetID() != source.PlanetID()) {
                int distance = Distance(source.PlanetID(), p.PlanetID());
                if (distance < min_distance) {
                    min_distance = distance;
                    closest = p;
                }
            }
        }
        return closest;
    }

    public Planet FarthestFrom(int sourcePlanet, List<Planet> planets) {
        int max_distance = Integer.MIN_VALUE;
        Planet farthest = null;
        for (Planet p : planets) {
            if (p.PlanetID() != sourcePlanet) {
                int distance = Distance(sourcePlanet, p.PlanetID());
                if (distance > max_distance) {
                    max_distance = distance;
                    farthest = p;
                }
            }
        }
        return farthest;
    }

    public Planet FarthestFrom(Planet source, List<Planet> planets) {
        int max_distance = Integer.MIN_VALUE;
        Planet farthest = null;
        for (Planet p : planets) {
            if (p.PlanetID() != source.PlanetID()) {
                int distance = Distance(source.PlanetID(), p.PlanetID());
                if (distance > max_distance) {
                    max_distance = distance;
                    farthest = p;
                }
            }
        }
        return farthest;
    }

    // Returns the distance between two planets, rounded up to the next highest
    // integer. This is the number of discrete time steps it takes to get
    // between the two planets.
    public int Distance(int sourcePlanet, int destinationPlanet) {
        Planet source = planets.get(sourcePlanet);
        Planet dest = planets.get(destinationPlanet);
        return Distance(source, dest);
    }

    // Returns the distance between two planets, rounded up to the next highest
    // integer. This is the number of discrete time steps it takes to get
    // between the two planets.
    public int Distance(Planet source, Planet destination) {
        if (destination != null) {
            int destinationPlanet = destination.PlanetID();
            if (source.HasDistance(destinationPlanet)) {
                return source.GetDistance(destinationPlanet, planets);
            } else {
                if (destinationPlanet >= 0) {
                    return planets.get(destinationPlanet).GetDistance(source);
                } else {
                    return destination.GetDistance(source);
                }
            }
        }
        return Integer.MAX_VALUE;
    }

    public void Log(String s) {
        orders.add((new StringBuilder(s)).append("\n"));
    }

    public void Log(StringBuilder sb) {
        orders.add(sb.append("\n"));
    }

    public void Log(int i) {
        Log(Integer.toString(i));
    }

    public void Log(double d) {
        Log(Double.toString(d));
    }

    // Add a new Order to the orders ArrayList.
    public void CacheOrder(int sourcePlanet, int destinationPlanet, int numShips) {
        if (sourcePlanet != destinationPlanet && numShips > 0) {
            orders.add((new Order(sourcePlanet, destinationPlanet, numShips)).getStringBuilder());
            GetPlanet(sourcePlanet).RemoveShips(numShips);
            int distance = Distance(sourcePlanet, destinationPlanet);
            Fleet f = new Fleet(1,
                    numShips,
                    sourcePlanet,
                    destinationPlanet,
                    distance,
                    distance);
            AddFleet(f);
        }
    }

    // Add a new Order to the orders ArrayList.
    public void CacheOrder(Planet source, Planet dest, int numShips) {
        if (source.PlanetID() != dest.PlanetID() && numShips > 0) {
            orders.add((new Order(source.PlanetID(), dest.PlanetID(), numShips)).getStringBuilder());
            source.RemoveShips(numShips);
            int distance = Distance(source.PlanetID(), dest.PlanetID());
            Fleet f = new Fleet(1,
                    numShips,
                    source.PlanetID(),
                    dest.PlanetID(),
                    distance,
                    distance);
            AddFleet(f);
        }
    }

    // Issues all Orders in orders and clears the ArrayList.
    public void IssueCachedOrders() {
        if (orders.size() > 0) {
            StringBuilder sb = new StringBuilder();
            for (StringBuilder o : orders) {
                sb.append(o);
            }
            System.out.print(sb.toString());
            System.out.flush();
            orders.clear();
        }
    }

    // Sends an order to the game engine. An order is composed of a source
    // planet number, a destination planet number, and a number of ships. A
    // few things to keep in mind:
    //   * you can issue many orders per turn if you like.
    //   * the planets are numbered starting at zero, not one.
    //   * you must own the source planet. If you break this rule, the game
    //     engine kicks your bot out of the game instantly.
    //   * you can't move more ships than are currently on the source planet.
    //   * the ships will take a few turns to reach their destination. Travel
    //     is not instant. See the Distance() function for more info.
    public void IssueOrder(int sourcePlanet,
            int destinationPlanet,
            int numShips) {
        System.out.println("" + sourcePlanet + " " + destinationPlanet + " "
                + numShips);
        System.out.flush();
        GetPlanet(sourcePlanet).RemoveShips(numShips);
        int distance = Distance(sourcePlanet, destinationPlanet);
        Fleet f = new Fleet(1,
                numShips,
                sourcePlanet,
                destinationPlanet,
                distance,
                distance);
        AddFleet(f);
    }

    // Sends an order to the game engine. An order is composed of a source
    // planet number, a destination planet number, and a number of ships. A
    // few things to keep in mind:
    //   * you can issue many orders per turn if you like.
    //   * the planets are numbered starting at zero, not one.
    //   * you must own the source planet. If you break this rule, the game
    //     engine kicks your bot out of the game instantly.
    //   * you can't move more ships than are currently on the source planet.
    //   * the ships will take a few turns to reach their destination. Travel
    //     is not instant. See the Distance() function for more info.
    public void IssueOrder(Planet source, Planet dest, int numShips) {
        System.out.println("" + source.PlanetID() + " " + dest.PlanetID()
                + " " + numShips);
        System.out.flush();
        source.RemoveShips(numShips);
        int distance = Distance(source.PlanetID(), dest.PlanetID());
        Fleet f = new Fleet(1,
                numShips,
                source.PlanetID(),
                dest.PlanetID(),
                distance,
                distance);
        AddFleet(f);
    }

    // Sends the game engine a message to let it know that we're done sending
    // orders. This signifies the end of our turn.
    public void FinishTurn() {
        System.out.println("go");
        System.out.flush();
    }

    // Returns true if the named player owns at least one planet or fleet.
    // Otherwise, the player is deemed to be dead and false is returned.
    public boolean IsAlive(int playerID) {
        for (Planet p : planets) {
            if (p.Owner() == playerID) {
                return true;
            }
        }
        for (Fleet f : fleets) {
            if (f.Owner() == playerID) {
                return true;
            }
        }
        return false;
    }

    // If the game is not yet over (ie: at least two players have planets or
    // fleets remaining), returns -1. If the game is over (ie: only one player
    // is left) then that player's number is returned. If there are no
    // remaining players, then the game is a draw and 0 is returned.
    public int Winner() {
        Set<Integer> remainingPlayers = new TreeSet<Integer>();
        for (Planet p : planets) {
            remainingPlayers.add(p.Owner());
        }
        for (Fleet f : fleets) {
            remainingPlayers.add(f.Owner());
        }
        switch (remainingPlayers.size()) {
            case 0:
                return 0;
            case 1:
                return ((Integer) remainingPlayers.toArray()[0]).intValue();
            default:
                return -1;
        }
    }

    // Returns the number of ships that the current player has, either located
    // on planets or in flight.
    public int NumShips(int playerID) {
        return NumShipsOnPlanets(playerID) + NumShipsInFlight(playerID);
    }

    public int NumShips(List<Fleet> fleets) {
        int ships = 0;
        for (Fleet f : fleets) {
            ships += f.NumShips();
        }
        return ships;
    }

    public int NumShipsOnPlanets(int playerID) {
        int numShips = 0;
        for (Planet p : planets) {
            if (p.Owner() == playerID) {
                numShips += p.NumShips();
            }
        }
        return numShips;
    }

    public int NumShipsInFlight(int playerID) {
        int numShips = 0;
        for (Fleet f : fleets) {
            if (f.Owner() == playerID) {
                numShips += f.NumShips();
            }
        }
        return numShips;
    }

    //Returns the sum of each of the player's growth rates
    public int Production(int playerID) {
//        int growthRate = 0;
//        for (Planet p : planets) {
//            if (p.Owner() == playerID) {
//                growthRate += p.GrowthRate();
//            }
//        }
//        return growthRate;

        switch(playerID){
        case 1:
            return myProduction;
        default:
           return enemyProduction;
        }
    }

    public void GrowPlanets() {
        for (Planet p : planets) {
            if (p.Owner() != 0) {
                p.AddShips(p.GrowthRate());
            }
        }

    }

    //Return the planet's strength, taking into account fleets headed to it
    public int PlanetNetStrength(Planet p) {
        int strength = p.NumShips();
        if (p.Owner() != 1) {
            strength *= -1;
        }
        for (Fleet f : fleets) {
            if (f.DestinationPlanet() == p.PlanetID()) {
                if (f.Owner() == 1) {
                    strength = strength + f.NumShips();
                } else {
                    strength = strength - f.NumShips();
                }
            }
        }
        return strength;
    }

    //Return the planet's strength, taking into account fleets headed to it
    public int PlanetNetStrength(int planetID) {
        Planet p = GetPlanet(planetID);
        int strength = p.NumShips();
        if (p.Owner() != 1) {
            strength *= -1;
        }
        for (Fleet f : fleets) {
            if (f.DestinationPlanet() == p.PlanetID()) {
                if (f.Owner() == 1) {
                    strength = strength + f.NumShips();
                } else {
                    strength = strength - f.NumShips();
                }
            }
        }
        return strength;
    }

    public double PlanetValue(Planet source, Planet target, double distanceWeight, double growthWeight, double strengthWeight) {
        double value = 0;
        if (target.GrowthRate() < 1) {
            return Integer.MIN_VALUE;
        }

        int strength = PredictedStrength(target, Distance(source, target));

        double avgDistance = 0;
        for (Planet p : myPlanets) {
            avgDistance += p.GetDistance(target);
        }
        avgDistance = avgDistance / myPlanets.size();

        //distance is multiplied by -1 because high distance is bad
        value = strength * strengthWeight * (-1) + avgDistance * distanceWeight + target.GrowthRate() * growthWeight * (-1);

        return value;
    }

    public double PlanetValue(Coord source, Planet target, double distanceWeight, double growthWeight, double strengthWeight) {
        double value = 0;
        if (target.GrowthRate() < 1) {
            return Integer.MIN_VALUE;
        }
        Planet fakeSource = new Planet(-1, -1, -1, -1, source.X(), source.Y());
        int strength = PredictedStrength(target, Distance(fakeSource, target));

        double avgDistance = 0;
        for (Planet p : myPlanets) {
            avgDistance += p.GetDistance(target);
        }
        avgDistance = avgDistance / myPlanets.size();

        //distance is multiplied by -1 because high distance is bad
        value = strength * strengthWeight * (-1) + avgDistance * distanceWeight + target.GrowthRate() * growthWeight * (-1);

        return value;
    }

    public double PlanetValue(int source, int target, double distanceWeight, double growthWeight, double strengthWeight) {
        return PlanetValue(planets.get(source), planets.get(target), distanceWeight, growthWeight, strengthWeight);
    }

    public List<Integer> PredictedStrengthOverNTurns(Planet p, int N) {
        List<Integer> predictedValues = new ArrayList<Integer>();
        for (int i = 0; i < N; i++) {
            predictedValues.add(PredictedStrength(p, i));
        }
        return predictedValues;
    }

    public int PredictedStrength(Planet p, int turns) {
        int currentStrength = p.NumShips();
        if (p.Owner() != 1) {
            currentStrength *= -1;
        }
        List<Fleet> allFleets = Fleets();
        if (allFleets != null) {
            HashMap<Integer, ArrayList<Fleet>> incoming = new HashMap<Integer, ArrayList<Fleet>>();
            for (int i = 0; i < MapSize(); i++) {
                incoming.put(i, new ArrayList<Fleet>());
            }

            for (Fleet f : fleets) {

                if (f.DestinationPlanet() == p.PlanetID()) {
                    if (incoming.containsKey(f.TurnsRemaining())) {
                        List<Fleet> tempfleets = incoming.get(f.TurnsRemaining());
                        tempfleets.add(f);
                    }
                }
            }

            int owner = p.Owner();
            for (int i = 0; i < turns; i++) {
                if (owner == 1) {
                    currentStrength += p.GrowthRate();
                } else if (owner != 0) {
                    currentStrength -= p.GrowthRate();
                }
                List<Fleet> tempfleets = incoming.get(i);
                if (tempfleets != null) {
                    int neutralStrength = 0;
                    int enemyStrength = 0;
                    int myStrength = 0;
                    if (owner == 0) {
                        neutralStrength = currentStrength;
                    } else if (owner == 1) {
                        myStrength = currentStrength;
                    } else {
                        enemyStrength = currentStrength;
                    }
                    for (Fleet f : tempfleets) {
                        if (f.Owner() == 1) {
                            myStrength += f.NumShips();
                        } else {
                            enemyStrength -= f.NumShips();
                        }
                    }
                    int difference = myStrength + enemyStrength;
                    //i take control
                    if (difference > 0) {
                        currentStrength = difference + neutralStrength;
                        if (currentStrength > 0) {
                            owner = 1;
                        } else {
                            owner = 0;
                        }
                    } //the enemy takes control
                    else if (difference < 0) {
                        currentStrength = difference - neutralStrength;
                        if (currentStrength > 0) {
                            owner = 2;
                        } else {
                            owner = 0;
                            currentStrength *= -1;
                        }
                    }
                }
            }
        }
        return currentStrength;
    }

    public int PlanetNetStrengthPlusGrowthTimesDistance(Planet source, Planet target) {
        int strength = PlanetNetStrength(target);

        //if it's neutral
        if (target.Owner() == 0) {
            return strength;
        } //if it's mine
        else if (target.Owner() == 1) {
            strength += target.GrowthRate() * (Distance(source, target) + 1);
        } //if it's an enemy's
        else {
            strength -= target.GrowthRate() * (Distance(source, target) + 1);
        }
        return strength;
    }

    public int PlanetNetStrengthPlusGrowthTimesDistance(int sourceID, int targetID) {
        Planet source = GetPlanet(sourceID);
        Planet target = GetPlanet(targetID);
        int strength = PlanetNetStrength(target);

        //if it's neutral
        if (target.Owner() == 0) {
            return strength;
        } //if it's mine
        else if (target.Owner() == 1) {
            strength += target.GrowthRate() * (Distance(source, target) + 1);
        } //if it's an enemy's
        else {
            strength -= target.GrowthRate() * (Distance(source, target) + 1);
        }
        return strength;
    }

    public void MoveFleets() {
        List<Fleet> deadFleets = new ArrayList<Fleet>();
        for (Fleet f : fleets) {
            f.TimeStep();
            //Arrived at destination
            if (f.TurnsRemaining() <= 1) {
                //Enemy or Neutral planet
                Planet d = GetPlanet(f.DestinationPlanet());
                if (f.Owner() != d.Owner()) {
                    int r = f.NumShips() - d.NumShips();
                    //Successful Capture
                    if (r > 0) {
                        //Planet changes hands
                        d.Owner(f.Owner());
                        d.NumShips(r);
                    } else {
                        //subtract number of ships
                        d.RemoveShips(f.NumShips());
                    }
                } else {
                    //This is a reinforcement
                    //Add ships from fleet to planet
                    d.AddShips(f.NumShips());
                }
                //Remove fleet from fleets
                deadFleets.add(f);
            }
        }
        for (Fleet f : deadFleets) {
            RemoveFleet(f);
        }

    }

    public double Angle(double x, double y) {
        double angle;
        angle = Math.acos(((x * 1) + (y * 1)) / (Math.sqrt((double) (x * x + y * y)) * Math.sqrt(2.0)));
        angle *= (180 / Math.PI);
        return angle;
    }

    public double AveragePlanetStrength(List<Planet> planets) {
        double average = 0;
        for (Planet p : planets) {
            average += p.NumShips();
        }
        return average / planets.size();
    }

    //Decide where a planet goes
    private void AddPlanet(Planet p) {
        planets.add(p);
    }

    //Decide where a fleet goes
    private void AddFleet(Fleet f) {
        if (f.NumShips() > 0) {
            fleets.add(f);
            int owner = f.Owner();
            if (owner == 1) {
                myFleets.add(f);
            } else {
                enemyFleets.add(f);
            }
        }
    }

    public List<Fleet> FriendlyFleets(List<Fleet> fleets) {
        List<Fleet> friendlies = new ArrayList<Fleet>();
        for (Fleet f : fleets) {
            if (f.Owner() == 1) {
                friendlies.add(f);
            }
        }
        return friendlies;
    }

    public List<Fleet> FleetsGoingToPlanet(Planet p) {
        List<Fleet> pFleets = new ArrayList<Fleet>();
        for (Fleet f : fleets) {
            if (f.DestinationPlanet() == p.PlanetID()) {
                pFleets.add(f);
            }
        }
        return pFleets;
    }

    public List<Fleet> FleetsGoingToPlanet(Planet p, List<Fleet> fleets) {
        List<Fleet> pFleets = new ArrayList<Fleet>();
        for (Fleet f : fleets) {
            if (f.DestinationPlanet() == p.PlanetID()) {
                pFleets.add(f);
            }
        }
        return pFleets;
    }

    public List<Fleet> FleetsGoingToPlanet(int planetID) {
        Planet p = planets.get(planetID);
        return FleetsGoingToPlanet(p);
    }

    public List<Fleet> FleetsLeavingFromPlanet(Planet p) {
        List<Fleet> pFleets = new ArrayList<Fleet>();
        for (Fleet f : fleets) {
            if (f.SourcePlanet() == p.PlanetID()) {
                pFleets.add(f);
            }
        }
        return pFleets;
    }

    public List<Fleet> FleetsLeavingFromPlanet(int planetID) {
        Planet p = planets.get(planetID);
        return FleetsLeavingFromPlanet(p);
    }

    public List<Planet> PlanetsWithinRadius(Planet planet, int radius, List<Planet> planetList) {
        List<Planet> planetsToReturn = new ArrayList<Planet>();
        for (Planet p : planetList) {
            if (planet.GetDistance(p) <= radius) {
                planetsToReturn.add(p);
            }
        }
        return planetsToReturn;
    }

    public boolean ContainsEnemyPlanet(List<Planet> planets) {
        for (Planet p : planets) {
            if (p.Owner() == 2) {
                return true;
            }
        }
        return false;
    }

    public List<Planet> PlanetsOutsideRadius(Planet planet, int radius, List<Planet> planetList) {
        List<Planet> planetsToReturn = new ArrayList<Planet>();
        for (Planet p : planetList) {
            if (planet.GetDistance(p) > radius) {
                planetsToReturn.add(p);
            }
        }
        return planetsToReturn;
    }

    public double MapHeight() {
        double minY = Double.MAX_VALUE;
        double maxY = Double.MIN_VALUE;
        for (Planet p : planets) {
            double y = p.Y();
            if (y < minY) {
                minY = y;
            } else if (y > maxY) {
                maxY = y;
            }
        }
        return maxY - minY;
    }

    public double MapWidth() {
        double minX = Double.MAX_VALUE;
        double maxX = Double.MIN_VALUE;
        for (Planet p : planets) {
            double x = p.X();
            if (x < minX) {
                minX = x;
            } else if (x > maxX) {
                maxX = x;
            }
        }
        return maxX - minX;
    }

    public double MapSize() {
        return Math.sqrt(MapHeight() * MapHeight() + MapWidth() * MapWidth());
    }

    // Parses a game state from a string. On success, returns 1. On failure,
    // returns 0.
    public int ParseGameState(String s) {
        turn++;

        //can't be cached
        fleets.clear();
        enemyFleets.clear();
        myFleets.clear();

        //could be cached?
        myPlanets.clear();
        neutralPlanets.clear();
        notMyPlanets.clear();
        enemyPlanets.clear();

        myProduction = 0;
        enemyProduction = 0;

        int planetID = 0;
        String[] lines = s.split("\n");
        for (int i = 0; i < lines.length; ++i) {
            String line = lines[i];
            int commentBegin = line.indexOf('#');
            if (commentBegin >= 0) {
                line = line.substring(0, commentBegin);
            }
            if (line.trim().length() == 0) {
                continue;
            }
            String[] tokens = line.split(" ");
            if (tokens.length == 0) {
                continue;
            }
            if (tokens[0].equals("P")) {
                if (tokens.length != 6) {
                    return 0;
                }
                Planet p = null;
                if (turn == 1) {
                    double x = Double.parseDouble(tokens[1]);
                    double y = Double.parseDouble(tokens[2]);
                    int owner = Integer.parseInt(tokens[3]);
                    int numShips = Integer.parseInt(tokens[4]);
                    int growthRate = Integer.parseInt(tokens[5]);
                    p = new Planet(planetID++,
                            owner,
                            numShips,
                            growthRate,
                            x, y);
                    AddPlanet(p);
                } else {
                    p = planets.get(planetID++);
                    p.NumShips(Integer.parseInt(tokens[4]));
                    p.Owner(Integer.parseInt(tokens[3]));
                }
                if (p != null) {
                    int owner = p.Owner();
                    switch (owner) {
                        case 0:
                            neutralPlanets.add(p);
                            notMyPlanets.add(p);
                            break;
                        case 1:
                            myPlanets.add(p);
                            myProduction += p.GrowthRate();
                            break;
                        default:
                            enemyPlanets.add(p);
                            enemyProduction += p.GrowthRate();
                            notMyPlanets.add(p);
                            break;
                    }
                }
            } else if (tokens[0].equals("F")) {
                if (tokens.length != 7) {
                    return 0;
                }
                int owner = Integer.parseInt(tokens[1]);
                int numShips = Integer.parseInt(tokens[2]);
                int source = Integer.parseInt(tokens[3]);
                int destination = Integer.parseInt(tokens[4]);
                int totalTripLength = Integer.parseInt(tokens[5]);
                int turnsRemaining = Integer.parseInt(tokens[6]);
                Fleet f = new Fleet(owner,
                        numShips,
                        source,
                        destination,
                        totalTripLength,
                        turnsRemaining);
                AddFleet(f);
            } else {
                return 0;
            }
        }
        return 1;
    }

    // Loads a map from a text file. The text file contains a description of
    // the starting state of a game. See the project wiki for a description of
    // the file format. It should be called the Planet Wars Point-in-Time
    // format. On success, return 1. On failure, returns 0.
    private int LoadMapFromFile(String mapFilename) {
        String s = "";
        BufferedReader in = null;
        try {
            in = new BufferedReader(new FileReader(mapFilename));
            int c;
            while ((c = in.read()) >= 0) {
                s += (char) c;
            }
        } catch (Exception e) {
            return 0;
        } finally {
            try {
                in.close();
            } catch (Exception e) {
                // Fucked.
            }
        }
        return ParseGameState(s);
    }
}
